package main

/*
给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
*/
func main() {
	word1 := "sea"
	word2 := "east"

	println(minDistance(word1, word2))
}

/**
 *	minDistance
 *	@Description: 动态规划
 *	@param word1 string
 *	@param word2 string
 *	@return min int
 */
func minDistance(word1 string, word2 string) (min int) {
	n1 := len(word1)
	n2 := len(word2)
	m := make([][]int, n1+1)
	for i := range m {
		m[i] = make([]int, n2+1)
	}

	for i := range word1 {
		for j := range word2 {
			if word1[i] == word2[j] {
				m[i+1][j+1] = m[i][j] + 1
			} else {
				m[i+1][j+1] = max(m[i][j+1], m[i+1][j])
			}
		}
	}

	maxLen := m[n1][n2]

	return n1 + n2 - maxLen*2
}

func max(i, j int) int {
	if i > j {
		return i
	}
	return j
}
